package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/delete-n-nodes-after-m-nodes-of-a-linked-list'>删除链表 M 个节点之后的 N 个节点(Delete N Nodes After M Nodes of a Linked List)</a>
 * <p>
 * 给定链表 head 和两个整数 m 和 n. 遍历该链表并按照如下方式删除节点:
 *     <ul>
 *         <li>开始时以头节点作为当前节点.</li>
 *         <li>保留以当前节点开始的前 m 个节点.</li>
 *         <li>删除接下来的 n 个节点.</li>
 *         <li>重复步骤 2 和 3, 直到到达链表结尾.</li>
 *     </ul>
 * </p>
 * <p>在删除了指定结点之后, 返回修改过后的链表的头节点.</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1:
 *      输入: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3
 *          1->2-><font color='red'>3->4->5</font>->6->7-><font color='red'>8->9->10</font>->11->12-><font color='red'>13</font>
 *      输出: [1,2,6,7,11,12]
 *          1->2->6->7->11->12
 *      解析： 保留前(m = 2)个结点,  也就是以黑色节点表示的从链表头结点开始的结点(1 ->2).
 *            删除接下来的(n = 3)个结点(3 -> 4 -> 5), 在图中以红色结点表示.
 *            继续相同的操作, 直到链表的末尾.
 *            返回删除结点之后的链表的头结点.
 *
 *  示例 2:
 *      输入: head = [1,<font color='red'>2,3,4</font>,5,<font color='red'>6,7,8</font>,9,<font color='red'>10,11</font>], m = 1, n = 3
 *      输出: [1,5,9]
 *      解析: 返回删除结点之后的链表的头结点.
 *
 *  示例 3:
 *      输入: head = [1,2,3,<font color='red'>4</font>,5,6,7,<font color='red'>8</font>,9,10,11], m = 3, n = 1
 *      输出: [1,2,3,5,6,7,9,10,11]
 *
 *  示例 4:
 *      输入: head = [9,<font color='red'>3,7</font>,7,<font color='red'>9,10</font>,8,<font color='red'>2</font>], m = 1, n = 2
 *      输出: [9,7,8]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表中节点数目在范围 [1, 10^4] 内</li>
 *     <li>1 <= Node.val <= 10^6</li>
 *     <li>1 <= m, n <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/13 16:43
 */
public class LC1474DeleteNNodesAfterMNodesOfALinkedList_S {
    static class Solution {
        public ListNode deleteNodes(ListNode head, int m, int n) {
            ListNode dummyHead = new ListNode(-1, head);
            ListNode currNode = dummyHead;
            while (currNode.next != null) {
                for (int i = 0; i < m && currNode.next != null; i++) {
                    currNode = currNode.next;
                }
                for (int i = 0; i < n && currNode.next != null; i++) {
                    currNode.next = currNode.next.next;
                }
            }
            return dummyHead.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListNode(solution.deleteNodes(Generator.create(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13), 2, 3));
        Printer.printListNode(solution.deleteNodes(Generator.create(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11), 1, 3));
        Printer.printListNode(solution.deleteNodes(Generator.create(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11), 3, 1));
        Printer.printListNode(solution.deleteNodes(Generator.create(9, 3, 7, 7, 9, 10, 8, 2), 1, 2));
        Printer.printListNode(solution.deleteNodes(Generator.create(9), 1, 1));
        Printer.printListNode(solution.deleteNodes(Generator.create(9), 2, 1));
    }
}
